package ds.tree.binarytree.app;

import ds.tree.binarytree.BinaryTree;
import ds.tree.binarytree.Node;

public class PostPolynomialAnalizer {

	private BinaryTree resultTree;
	
	public PostPolynomialAnalizer(String expression)
	{
		java.util.Stack<BinaryTree> treeStack = new java.util.Stack<BinaryTree>();
		for(int i=0;i<expression.length();i++)
		{
			char ch = expression.charAt(i);
			switch(ch)
			{
			case '+':
			case '-':
			case '*':
			case '/':
				BinaryTree paramTree2 = treeStack.pop();
				BinaryTree paramTree1 = treeStack.pop();
				
				BinaryTree newTree = new BinaryTree(ch);
				newTree.setLeftSubTree(paramTree1);
				newTree.setRightSubTree(paramTree2);
				
				treeStack.push(newTree);
				break;
			default:
				treeStack.push(new BinaryTree(ch));
				break;
			}
		}
		resultTree = treeStack.pop();
	}
	
	public String getInExpression() // 中序遍历
	{
		StringBuffer sbuffer = new StringBuffer();
		getInExpression(resultTree.getRoot(), sbuffer);
		return sbuffer.toString();
	}
	
	private void getInExpression(Node node,StringBuffer sbuffer)
	{
		if(node == null)
			return;
		
		char ch = (char)node.getIData();
		if(ch == '+' || ch == '-')
		{
			sbuffer.append("(");
		}
		
		getInExpression(node.getLeftChild(), sbuffer);
		sbuffer.append((char)node.getIData());
		getInExpression(node.getRightChild(), sbuffer);
		
		if(ch == '+' || ch == '-')
		{
			sbuffer.append(")");
		}
	}
	
	public String getPreExpression()
	{
		StringBuffer sbuffer = new StringBuffer();
		getPreExpression(resultTree.getRoot(), sbuffer);
		return sbuffer.toString();
	}
	
	private void getPreExpression(Node node,StringBuffer sbuffer)
	{
		if(node == null)
			return;
		sbuffer.append((char)node.getIData());
		getPreExpression(node.getLeftChild(), sbuffer);
		getPreExpression(node.getRightChild(), sbuffer);
	}
}

class PostPolynomialAnalizerApp
{
	public static void main(String args[])
	{
		PostPolynomialAnalizer pa= new PostPolynomialAnalizer("ABC+*D-");
		System.out.println(pa.getInExpression());
		System.out.println(pa.getPreExpression());
	}
}
